package com.hanxiaozhang.no10leetcode.tree;

import org.apache.poi.ss.formula.functions.T;

/**
 * 〈一句话功能简述〉<br>
 * 〈判断一棵二叉树是否是平衡树〉
 * 平衡树就是指这棵树的左子树和右子树高度差不大于1
 * <p>
 * 实例1：
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：true
 * 实例2：
 * 输入：root = [1,2,2,3,3,null,null,4,4]
 * 输出：false
 *
 * @author hanxinghua
 * @create 2024/4/12
 * @since 1.0.0
 */
public class No110BalancedBinaryTree {


    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(3);
        tree1.left = new TreeNode(9);
        tree1.right = new TreeNode(20);
        tree1.right.left = new TreeNode(15);
        tree1.right.right = new TreeNode(7);

        TreeNode tree2 = new TreeNode(1);
        tree2.left = new TreeNode(2);
        tree2.right = new TreeNode(2);
        tree2.left.left = new TreeNode(3);
        tree2.left.right = new TreeNode(3);
        tree2.left.left.left = new TreeNode(4);
        tree2.left.left.right = new TreeNode(4);


        System.out.println(method1(tree1));
        System.out.println(method1(tree2));


    }

    /**
     * 方法1
     * 思路：
     * 整体：递归计算每个节点左右子树的高度差，是否小于1。
     *
     * @param root
     * @return
     */
    private static boolean method1(TreeNode root) {
        if (root == null) {
            return true;
        }
        return method1(root.left)
                && method1(root.right)
                && Math.abs(getDeep(root.left) - getDeep(root.right)) <= 1;
    }


    /**
     * 获取深度
     *
     * @param root
     * @return
     */
    private static Integer getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getDeep(root.left), getDeep(root.right)) + 1;
    }


}
